package com.demo.study.algorithm.sorts;

import static com.demo.study.utils.ArrayUtil.*;

/**
 * 堆排序：在选择排序的基础上进行优化，使用堆的特性，快速找到最大值（或最小值）进行替换
 *
 * @author Baymax
 * @since 2024-08-15
 */
public class B03_HeapSort {
    public static void main(String[] args) {
        int[] nums = intRandomArray();
        printArray(nums);
        heapSort(nums);
        printArray(nums);
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] nums) {
        // 1. 先建堆
        heapify(nums, nums.length);
        // 2.交互
        for (int right = nums.length - 1; right > 0; right--) {
            swap(nums, 0, right); // 使用堆顶最大元素和未排序的最后一个元素交换
            downWhile(nums, 0, right); // 结构发生改变，重新下潜
        }
    }

    // 建堆
    private static void heapify(int[] array, int size) {
        // i = size / 2 - 1 表示堆的最后一个非叶子节点
        for (int i = size / 2 - 1; i >= 0; i--) {
            downWhile(array, i, size);
        }
    }

    // 下沉-循环实现
    private static void downWhile(int[] array, int parent, int size) {
        while (true) {
            int left = parent * 2 + 1; // 左子树索引
            int right = left + 1; // 右子树索引
            int maxIndex = parent;
            if (left < size && array[left] > array[maxIndex]) {
                maxIndex = left;
            }
            if (right < size && array[right] > array[maxIndex]) {
                maxIndex = right;
            }
            if (maxIndex == parent) { // 找到了大的节点
                break;
            }
            swap(array, maxIndex, parent); // 交换位置
            parent = maxIndex;
        }
    }

    // 下沉-递归实现
    private static void down(int[] array, int parent, int size) {
        int left = parent * 2 + 1; // 左子树索引
        int right = left + 1; // 右子树索引
        int maxIndex = parent;
        if (left < size && array[left] > array[maxIndex]) {
            maxIndex = left;
        }
        if (right < size && array[right] > array[maxIndex]) {
            maxIndex = right;
        }
        if (maxIndex != parent) { // 找到了大的节点
            swap(array, maxIndex, parent); // 交换位置
            down(array, maxIndex, size); // 连续下沉
        }
    }
}
